package arithmetic.LeetCode;

import java.util.Arrays;
import java.util.Stack;

/**
 *https://leetcode.cn/problems/longest-valid-parentheses/description/?envType=study-plan-v2&envId=top-100-liked
 * 32. 最长有效括号
 * 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
 *
 *
 *
 * 示例 1：
 *
 * 输入：s = "(()"
 * 输出：2
 * 解释：最长有效括号子串是 "()"
 * 示例 2：
 *
 * 输入：s = ")()())"
 * 输出：4
 * 解释：最长有效括号子串是 "()()"
 * 示例 3：
 *
 * 输入：s = ""
 * 输出：0
 *
 * @author jiangfeng on 2024/1/16
 */
public class longestValidParentheses {
    public static void main(String[] args) {
        //        System.out.println(new Solution().longestValidParentheses("(()"));
        //        System.out.println(new Solution().longestValidParentheses("()(())"));
        //        System.out.println(new Solution().longestValidParentheses(")()())"));
        System.out.println(new Solution().longestValidParentheses("(()())"));
        //        System.out.println(new Solution().longestValidParentheses("("));
    }

    static class Solution {
        public int longestValidParentheses(String s) {
            // 动态规划
            if (s.length() < 2) {
                return 0;
            }
            int res = 0;
            // dp[i] 表示 在i处的最大值
            // 两个一检查 只有遇到 "()" 和 "))" 才开始递推迭代
            // 初始值默认就是0
            int[] dp = new int[s.length()];
            dp[1] = (s.charAt(0) == '(' && s.charAt(1) == ')') ? 2 : 0;
            res = dp[1];
            for (int i = 2; i < s.length(); i++) {
                if (s.charAt(i) == ')') {
                    // 情况1：（）
                    if (s.charAt(i - 1) == '(') {
                        dp[i] = dp[i - 2] + 2;
                    } else {
                        // 情况2： ))
                        if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                            dp[i] = (i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] : 0) + dp[i - 1] + 2;
                        }
                    }
                    res = Math.max(dp[i], res);
                }
            }
            return res;
        }
    }


    static class Solution2 {
        public int longestValidParentheses(String s) {
            // 一边出栈一边排序，记录最大长度
            if (s.length() < 1) {
                return 0;
            }
            Stack<Integer> st = new Stack<>();
            st.push(-1);
            int res = 0;
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == '(') {
                    st.push(i);
                } else {
                    st.pop();
                    if (st.empty()) {
                        st.push(i);
                    } else {
                        // 遇到反括号计算一下
                        res = Math.max(res, i - st.peek());
                    }
                }
            }
            return res;
        }
    }

    static class Solution3 {
        public int longestValidParentheses(String s) {
            if (s.length() < 1) {
                return 0;
            }
            //使用栈计算出 序号相对应的顺序
            Stack<Integer> st = new Stack<>();
            int[] resArr = new int[s.length()];
            Arrays.fill(resArr, -2);
            int index = 0;
            for (int i = 0; i < s.length(); i++) {
                if (!st.isEmpty() && s.charAt(i) == ')') {
                    resArr[index++] = st.pop();
                    resArr[index++] = i;
                } else if (s.charAt(i) == '(') {
                    st.push(i);
                }
            }
            Arrays.sort(resArr);
            // 计算连续的最长
            index = 0;
            while (index < s.length() && resArr[index] == -2) {
                index++;
            }

            int maxLen = 0;
            int res = 0;
            while (index < (s.length() - 1)) {
                if (resArr[index + 1] - resArr[index] == 1) {
                    maxLen++;
                    res = Math.max(res, maxLen + 1);
                } else {
                    maxLen = 0;
                }
                index++;
            }

            return res;
        }

    }

    static class Solution1 {
        public int longestValidParentheses(String s) {
            // 子串表示 连续的子集。  （子序列可以不连续）
            // 开始必须是（
            int res = 0;
            Stack<Character> st = new Stack<>();
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == '(') {

                    //  先")" 后 来"("
                    if (st.empty() || st.peek() == ')') {
                        st.push('(');
                    } else {
                        // 不匹配，直接算长度结束了
                        res = Math.max(res, st.size() - 1);
                        st.clear();
                        st.push('(');
                    }

                } else {
                    // 先空或 ')' 直接清空
                    if (st.empty() || st.peek() == ')') {
                        res = Math.max(res, st.size());
                        st.clear();
                    } else {
                        st.push(')');
                    }
                }
            }
            return res;
        }
    }
}
